#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), ret = INT_MAX;
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for (int j = 0; j < n; j++) dp[0][j] = grid[0][j];
        for (int i = 1; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++) {
                    if (k == j) continue;
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + grid[i][j]);
                }
        for (int j = 0; j < n; j++) ret = min(ret, dp[n - 1][j]);
        return ret;
    }
};

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int first_min = 0, second_min = 0, first_min_index = -1, n = grid.size();
        for (int i = 0; i < n; i++)
        {
            int cur_first_min = INT_MAX, cur_second_min = INT_MAX, cur_first_min_index = -1;

            for (int j = 0; j < n; j++)
            {
                int cur = (j != first_min_index ? first_min : second_min) + grid[i][j];
                if (cur < cur_first_min) {
                    cur_second_min = cur_first_min;
                    cur_first_min = cur;
                    cur_first_min_index = j;
                }
                else if (cur < cur_second_min) cur_second_min = cur;
            }

            first_min = cur_first_min;
            first_min_index = cur_first_min_index;
            second_min = cur_second_min;
        }
        return first_min;
    }
};